package com.future;

import java.util.PriorityQueue;

/**
 * Description: 407. 接雨水 II（大厂刷题班22）
 *
 * @author weiruibai.vendor
 * Date: 2022/7/13 12:28
 */
public class Solution_407 {

    public static void main(String[] args) {
/*
        PriorityQueue<Node> queue = new PriorityQueue<Node>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.val == o2.val ? (o1.row == o2.row ? o1.col - o2.col : o1.row - o2.row) : o1.col - o2.val;
            }
        });
        queue.add(new Node(1, 2, 4));
        queue.add(new Node(1, 1, -4));
        System.out.println("弹出一个：" + queue.poll());
        queue.add(new Node(-1, 2, 10));
        queue.add(new Node(-1, 3, -110));
        System.out.println("弹出一个：" + queue.poll());*/
        int[][] heightMap = new int[][]{{1, 4, 3, 1, 3, 2}, {3, 2, 1, 3, 2, 4}, {2, 3, 3, 2, 3, 1}};
        //heightMap = new int[][]{{3, 3, 3, 3, 3}, {3, 2, 2, 2, 3}, {3, 2, 1, 2, 3}, {3, 2, 2, 2, 3}, {3, 3, 3, 3, 3}};

       /* heightMap = new int[][]{
                {12, 13, 1, 12},
                {13, 4, 13, 12},
                {13, 8, 10, 12},
                {12, 13, 12, 12},
                {13, 13, 13, 13}
        };*/
        System.out.println(trapRainWater2(heightMap));
    }

    /**
     * 思路：
     * 1、开始时，把二维数组在四边都放到小根堆里面，最多高度maxHeight设置为1
     * 2、遍历小根堆，每次弹出(保证每次把堆中值弹出最小值)popNode
     * --2.1 popNode记录着当前节点在二维数组中的位置和值，先计算MaxHeight-popNode，如果是负数，就为0
     * --2.2 然后把popNode的前后左右都放入小根堆中，需要判断节点是否已经访问过，只需要放未被访问过的，所以需要辅助数组记录哪些节点访问过（这就是记录当前节点位置的作用）
     * 3、步骤2循环遍历到空，就是最后的答案
     *
     * @param heightMap
     * @return
     */
    public static int trapRainWater2(int[][] heightMap) {
        int ans = 0;
        if (heightMap.length < 3) {
            return 0;
        }
        int M = heightMap.length;
        int N = heightMap[0].length;
        boolean[][] visited = new boolean[M][N];
        PriorityQueue<Node> queue = new PriorityQueue<Node>(((
                o1, o2) -> o1.val == o2.val ? (o1.row == o2.row ? o1.col - o2.col : o1.row - o2.row) : o1.val - o2.val));
        /**
         * 把数组四个边界都放到小根堆里
         */
        for (int i = 0; i < M; i++) {
            // 最左最右两列
            queue.add(new Node(i, 0, heightMap[i][0]));
            queue.add(new Node(i, N - 1, heightMap[i][N - 1]));
            visited[i][0] = true;
            visited[i][N - 1] = true;
        }
        for (int i = 0; i < N; i++) {
            // 最上最下两行
            queue.add(new Node(0, i, heightMap[0][i]));
            queue.add(new Node(M - 1, i, heightMap[M - 1][i]));
            visited[0][i] = true;
            visited[M - 1][i] = true;
        }

        int maxHeight = 0;
        while (!queue.isEmpty()) {
            Node popNode = queue.poll();
            ans += Math.max(maxHeight - popNode.val, 0);
            maxHeight = Math.max(popNode.val, maxHeight);
            int row = popNode.row;
            int col = popNode.col;
            // popNode上方
            if (row - 1 >= 0 && !visited[row - 1][col]) {
                visited[row - 1][col] = true;
                queue.add(new Node(row - 1, col, heightMap[row - 1][col]));
            }
            // popNode下方
            if (row + 1 < M && !visited[row + 1][col]) {
                visited[row + 1][col] = true;
                queue.add(new Node(row + 1, col, heightMap[row + 1][col]));
            }
            // popNode左边
            if (col - 1 >= 0 && !visited[row][col - 1]) {
                visited[row][col - 1] = true;
                queue.add(new Node(row, col - 1, heightMap[row][col - 1]));
            }
            // popNode右边
            if (col + 1 < N && !visited[row][col + 1]) {
                visited[row][col + 1] = true;
                queue.add(new Node(row, col + 1, heightMap[row][col + 1]));
            }
        }
        return ans;
    }

    private static class Node {
        // 记录该几点所在行
        public int col;
        // 记录该几点所在列
        public int row;
        // 该节点值
        public int val;

        public Node(int row, int col, int val) {
            this.row = row;
            this.col = col;
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "row=" + row +
                    ", col=" + col +
                    ", val=" + val +
                    '}';
        }
    }

}
